1.6 A new classification of complexity
尽管你桌上的台式电脑不是量子计算机，但它仍旧是个很厉害的设备：原理上，它能够执行任何想得到的（conceivable）计算。实际上有一些计算是无法完成的——要么时间太长，要么内存溢出。但如果你有一台内存无穷大的电脑，且愿意等待足够长时间，那么任何能够称作计算的工作都能由你手头这台小小的计算机完成。在这个意义上，我们称它是一台“通用计算机”（universal computer）。
经典的复杂性理论研究的是困难和容易问题的区分标准。通常来说，“困难”和“容易”是由需要多少时间或存储容量决定的。但如何定义有意义的区分标准，使得它不依赖于我们使用的硬件呢？真正的用来区分简单和困难计算问题的标准应该是普适的，它不以使用高性能还是老破旧的计算机而改变。
许多复杂性理论一般将算法的复杂性分为多项式时间(polynomial time)和指数时间(exponential time)。任意算法A，都可以定义复杂度，是用bit表示的算法输入值的长度。表示对任意N-bit输入所需的最长时间步，即最坏情况下的最长时间。比如，若算法A是质因数分解算法，那么就是最坏情况下分解一个N-bit数所需的时间步。多项式时间指的是，即解决问题所需的时间随N的增长不会快于的某个幂次。
如果不是多项式时间，则统称为指数时间。当然也有超多项式(superpolynomial)时间，随N的增长速度远比指数时间小，但也被误称为指数时间。这种是一种合理的区分问题难易的标准。但使用这种区分标准真正的原因是它不依赖于硬件，即不依赖于我们使用普通电脑还是超算。这种区分标准的普适性来自于计算机科学：不管在什么样的计算机上，如果你的运行时间是多项式时间，那么用我的计算机运行同样的算法也需要多项式时间；即使运算不了，我也可以仿真你的计算机每一个操作步骤，而这种仿真也只需要运行多项式时间，综合效果还是多项式时间。同样地，你的计算机也可以仿真我的，于是我们就能对哪个算法是多项式时间达成一致了。（当然，需要排除掉那些“不现实”的计算机，比如有无穷多个结点的并行计算机）。
如果量子计算机也能被这样仿真，像1.4节中所说的那样，那么量子计算机就只是技术上的进步了，却无法让经典计算机的多项式时间这个数学事实改变（量子计算机也只是多项式时间）。然而，Shor算法揭示了（并没有被证明），不可能用多项式时间来仿真一台量子计算机！这就改变了一切！对于经典的通用计算机，复杂性理论30余年来证明的这些定理，作为数学事实还是成立的。但复杂性理论也许不能作为真实的物理事实，因为经典的图灵机并不是一个恰当的能描述真实物理世界中运行的计算模型。
假如区分复杂性的量子标准和经典标准不一样（仅是猜测但未证实），那么这个结论会动摇计算机科学的基础。长远来看，它还会对技术进步产生深远影响。但它对物理学的重要性在哪儿？
我也不能确定。但是也许仅仅提到以下事实就足以让人印象深刻：目前没有哪个经典计算机能够精确预测哪怕只是中等数量qubits（100个的数量级）量子计算机的行为。这说明少量的qubits就有很大的潜力等待我们去挖掘。